Search results for "Recursively enumerable language"
showing 3 items of 3 documents
Co-learnability and FIN-identifiability of enumerable classes of total recursive functions
1994
Co-learnability is an inference process where instead of producing the final result, the strategy produces all the natural numbers but one, and the omitted number is an encoding of the correct result. It has been proved in [1] that co-learnability of Goedel numbers is equivalent to EX-identifiability. We consider co-learnability of indices in recursively enumerable (r.e.) numberings. The power of co-learnability depends on the numberings used. Every r.e. class of total recursive functions is co-learnable in some r.e. numbering. FIN-identifiable classes are co-learnable in all r.e. numberings, and classes containing a function being accumulation point are not co-learnable in some r.e. number…
Derived sets and inductive inference
1994
The paper deals with using topological concepts in studies of the Gold paradigm of inductive inference. They are — accumulation points, derived sets of order α (α — constructive ordinal) and compactness. Identifiability of a class U of total recursive functions with a bound α on the number of mindchanges implies \(U^{(\alpha + 1)} = \not 0\). This allows to construct counter-examples — recursively enumerable classes of functions showing the proper inclusion between identification types: EXα⊂EXα+1.
Inductive inference of recursive functions: Complexity bounds
2005
This survey includes principal results on complexity of inductive inference for recursively enumerable classes of total recursive functions. Inductive inference is a process to find an algorithm from sample computations. In the case when the given class of functions is recursively enumerable it is easy to define a natural complexity measure for the inductive inference, namely, the worst-case mindchange number for the first n functions in the given class. Surely, the complexity depends not only on the class, but also on the numbering, i.e. which function is the first, which one is the second, etc. It turns out that, if the result of inference is Goedel number, then complexity of inference ma…